package inner

// 堆排序
type HeapSort struct {
}

func (h *HeapSort) Sort(arr []int) []int {
	/*
		建堆意义：保证了堆的上一层level的数据一定大于或者小于下一层，方便后续整堆的时候，只需要关注于当前节点依次往下寻找
		建堆：tips:长度为n的数组，最后一个非叶子结点的index是: (n-1)/2
			推导：index为k的非叶子结点的左右孩子index分别是：2k+1=n、2k+2=n，所以为了求出确切的k值，index为n的孩子结点的父节点是：k=(n-1)/2
			应用：array最后一个叶子结点的index：n=len(array)-1，最后一个非叶子结点的index：（len(array)-1-1）/2 = len(array)/2-1
	*/
	for i := len(arr)/2 - 1; i >= 0; i-- {
		build(arr, i, len(arr))
	}

	// 整堆: i 遍历到1即可，不需要到0
	for i := len(arr) - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		build(arr, 0, i)
	}
	return arr
}

func build(array []int, curIndex, border int) {
	var (
		flag      = curIndex
		leftChild = curIndex*2 + 1
		rigtChild = curIndex*2 + 2
	)
	if border <= 0 || border > len(array) {
		return
	}

	if leftChild >= border { // left child
		return
	}
	if array[leftChild] > array[curIndex] {
		flag = leftChild
	}

	/* right child,
		注意：此处不同于left child，不能直接退出
	         此处右孩子对比的是最大的那个元素，可能是左孩子，也可能是curIndex
	*/
	if rigtChild < border && array[rigtChild] > array[flag] {
		flag = rigtChild
	}

	if flag != curIndex {
		array[curIndex], array[flag] = array[flag], array[curIndex]
		build(array, flag, border)
	}
}
